//
//  ProblemOffer55.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/5/23.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 55 - I. 二叉树的深度
 输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
 例如：
 给定二叉树 [3,9,20,null,null,15,7]，
     3
    / \
   9  20
     /  \
    15   7
 返回它的最大深度 3 。
 
 提示：
    节点总数 <= 10000
 */
@objcMembers class ProblemOffer55: NSObject {
    func solution() {
        let root = TreeNode(3)
        root.left = TreeNode(9)
        
        root.right = TreeNode(20)
        root.right?.left = TreeNode(15)
        root.right?.right = TreeNode(7)
        print(maxDepthGC(root))
    }
    
    /*
     深度 递归
     */
    func maxDepth(_ root: TreeNode?) -> Int {
        if root == nil {
            return 0
        }
        return max(maxDepth(root?.left), maxDepth(root?.right)) + 1
    }
    /*
     广度 数组
     改变root的val，用来记录当前的深度，例如：root.val = 1
     */
    func maxDepthG(_ root: TreeNode?) -> Int {
        if root == nil {
            return 0
        }
        root?.val = 1
        var list: [TreeNode?] = [root]
        var depth = 1
        var node: TreeNode? = nil
        while list.isEmpty == false {
            node = list.removeLast()
            
            // 处理left
            if node?.left != nil {
                node?.left?.val = node!.val + 1
                list.append(node?.left)
                depth = max(depth, node!.val + 1)
            }
            // 处理right
            if node?.right != nil {
                node?.right?.val = node!.val + 1
                list.append(node?.right)
                depth = max(depth, node!.val + 1)
            }
        }
        return depth
    }
    
    /*
     广度 数组
     每次记录一层
     */
    func maxDepthGC(_ root: TreeNode?) -> Int {
        if root == nil {
            return 0
        }
        
        var list:[TreeNode?] = [root]
        var sum = 0
        while list.isEmpty == false {
            // 统计当前层数的个数
            var n = list.count
            // 把当前层数的节点从数组中拿取
            while n > 0 {
                let node = list.removeFirst()
                
                // 如果有下一层，将下一层放入数组中
                if node?.left != nil {
                    list.append(node?.left)
                }
                
                if node?.right != nil {
                    list.append(node?.right)
                }
                
                n -= 1
            }
            
            sum += 1        // 增加当前层数
        }
        return sum
    }
}
